// ============================================================================
//
// Graph framework by Aurelien Moreau aurelien.moreau@gmail.com
// Modified by Pierre CHATEL chatelp@gmail.com
// Distributed under LGPL
// Copyright (C) Aurelien Moreau, 2008, 2009. All rights reserved
//
// ============================================================================

package com.thalesgroup.graphFramework.algorithms;

import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;

import com.thalesgroup.graphFramework.core.Edge;
import com.thalesgroup.graphFramework.core.Graph;
import com.thalesgroup.graphFramework.core.Vertex;

import com.thalesgroup.graphFramework.measure.Measure;

public class Dijkstra {

	static public <S, T> boolean compute(final Graph<S, T> graph,
			final Vertex<S, T> src) {
		final Measure<T> measure = new Measure<T>() {
			public double eval(T t) {
				return 1;
			}
		};
		return compute(graph, src, measure);
	}

	static public <S, T> boolean compute(final Graph<S, T> graph,
			final Vertex<S, T> src, final Measure<T> measure) {

		// init
		for(Iterator<Vertex<S,T>> is=graph.getVertices(); is.hasNext();) {
			Vertex<S,T> s=is.next();
			s.setUserFeature(LeastPathCost.W, Double.MAX_VALUE);
			s.setUserFeature(LeastPathCost.PI, null);
		}
		src.setUserFeature(LeastPathCost.W, 0.);

		// Dijkstra
		final Comparator<Vertex<S, T>> comp = new Comparator<Vertex<S, T>>() {
			public int compare(Vertex<S, T> u, Vertex<S, T> v) {
				double du = (Double) u.getUserFeature(LeastPathCost.W);
				double dv = (Double) v.getUserFeature(LeastPathCost.W);
				return Double.compare(du, dv);
			}
		};

		final LinkedList<Vertex<S, T>> F = new LinkedList<Vertex<S, T>>();
		for(Iterator<Vertex<S,T>> iv=graph.getVertices(); iv.hasNext();) {
			F.add(iv.next());
		}
		Collections.sort(F, comp);

		while (F.size() > 0) {
			final Vertex<S, T> u = F.remove(0);
			for(Iterator<Edge<S,T>> ie=u.getOuts(); ie.hasNext();) {
				Edge<S,T> e=ie.next();
				final Vertex<S, T> v = e.getOut();
				if (relaxation(u, v, measure)) {

					F.remove(v);
					int index = Collections.binarySearch(F, v, comp);
					if (index < 0) {
						F.add(-index - 1, v);
					} else {
						F.add(index, v);
					}
				}

			}
		}

		return true;
	}

	static public <S, T> boolean relaxation(final Vertex<S, T> u,
			final Vertex<S, T> v, final Measure<T> measure) {
		final double w_uv = measure.eval(u.getGraph().getEdge(u, v).getEdge());
		final double tmp = ((Double) u.getUserFeature(LeastPathCost.W)) + w_uv;
		if (((Double) v.getUserFeature(LeastPathCost.W)) > tmp) {
			v.setUserFeature(LeastPathCost.W, tmp);
			v.setUserFeature(LeastPathCost.PI, u);
			return true;
		} else {
			return false;
		}
	}

}
